package matrix;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author kaho
 * @since 2020/12/26
 */
public class _85_最大矩形 {


    /**
     * 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
     * @param matrix
     * @return
     */
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int columnSize = matrix[0].length;
        int[] height = new int[columnSize];
        int res = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < columnSize; j++) {
                if (matrix[i][j] == '1'){
                    height[j]++;
                }else {
                    height[j] = 0;
                }
            }
            res = Math.max(largestRectangleArea(height), res);
        }
        return res;
    }

    public int largestRectangleArea(int[] heights) {
        if (heights.length == 0) {
            return 0;
        }
        if (heights.length == 1) {
            return heights[0];
        }

        int res = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[stack.peekLast()] > heights[i]){
                int curHeight = heights[stack.pollLast()];
                while (!stack.isEmpty() && curHeight == heights[stack.peekLast()]){
                    stack.pollLast();
                }
                int wid;
                if (stack.isEmpty()) {
                    wid = i;
                }else {
                    wid = i - stack.peekLast() - 1;
                }
                res = Math.max(res, wid * curHeight);
            }
            stack.addLast(i);
        }

        while (!stack.isEmpty()) {
            int curHigh = heights[stack.pollLast()];
            while (!stack.isEmpty() && curHigh == heights[stack.peekLast()]){
                stack.pollLast();
            }
            int wid;
            if (stack.isEmpty()) {
                wid = heights.length;
            }else {
                wid = heights.length - stack.peekLast() - 1;
            }
            res = Math.max(res, wid * curHigh);
        }
        return res;
    }
}
